/*********************************************************************
 * Copyright (C) 2008 by Duncan A. Buell.  All rights reserved.
 * Class to implement a Doubly Linked List.
 * @author Duncan A. Buell
 * @version 1.00 2008-12-16
**/
public class DLL implements IDLL
{
/*********************************************************************
 * Instance variables for this class.
**/
  private int size;        /** list size, counting head and tail */
  private DLLNode head;    /** the head node of the list         */
  private DLLNode tail;    /** the tail node of the list         */

/*********************************************************************
 * Constructor.
**/
  public DLL()
  {
    this.setHead(new DLLNode());
    this.setTail(new DLLNode());
    head.setNext(this.tail);
    tail.setPrev(this.head);
    this.setSize(2);
  } // public DLL()

/*********************************************************************
 * Accessors and mutators.
**/
/*********************************************************************
 * Method to get the <code>head</code>.
 * @return the node that is the value of <code>head</code>.
**/
  public DLLNode getHead()
  {
    return this.head;
  } // public DLLNode getHead()

/*********************************************************************
 * Method to set the <code>head</code>.
 * @param value the value to be used
**/
  public void setHead(DLLNode value)
  {
    this.head = value;
  } // private void setHead(DLLNode value)

/*********************************************************************
 * Method to get the <code>size</code>.
 * @return the value of <code>size</code>.
**/
  public int getSize()
  {
    return this.size;
  } // public int getSize()

/*********************************************************************
 * Method to decrement the <code>size</code>.
 * We include this as a mutator because it will be used as if a
 * 'set' operation.
**/
  private void decSize()
  {
    this.setSize(this.size - 1);
  } // private void decSize()

/*********************************************************************
 * Method to increment the <code>size</code>.
 * We include this as a mutator because it will be used as if a
 * 'set' operation.
**/
  private void incSize()
  {
    this.setSize(this.size + 1);
  } // private void incSize()

/*********************************************************************
 * Method to set the <code>size</code>.
 * @param value the value to be used
**/
  public void setSize(int value)
  {
    this.size = value;
  } // private void setSize(int value)

/*********************************************************************
 * Method to get the <code>tail</code>.
 * @return the node that is the value of <code>tail</code>.
**/
  public DLLNode getTail()
  {
    return this.tail;
  } // public DLLNode getTail()

/*********************************************************************
 * Method to set the <code>tail</code>.
 * @param value the value to be used
**/
  public void setTail(DLLNode value)
  {
    this.tail = value;
  } // private void setTail(DLLNode value)

/*********************************************************************
 * General methods.
**/
/*********************************************************************
 * Method to add a node.
 * By default this adds the node at the head.
 * We deliverately fail to bulletproof w.r.t. the return value.
 * @param dllData the <code>Record</code> data item to add.
**/
  public boolean add(Record dllData)
  {
    this.addAtTail(dllData);
    return true;
  } // public boolean add(Record dllData)

/*********************************************************************
 * Method to add a node at the tail of a linked list. 
 * @param newNode the <code>DLLNode</code> node to add. 
**/
  private void addAtTail(Record dllData)
  {

	  DLLNode temp=new DLLNode(dllData);
	 
	  temp.setNext(tail);
	  temp.setPrev(tail.getPrev());
	  tail.getPrev().setNext(temp);
	  tail.setPrev(temp);
	  
	  size++;
	
  } // private void addAtTail(Record dllData)

/*********************************************************************
 * Method to find if a list has a given data item. 
 * @param dllData the <code>Record</code> to match against. 
 * @return the <code>boolean</code> answer to the question.
**/
  public boolean contains(Record dllData)
  {
    boolean returnValue = false;
    DLLNode foundNode = null;
    foundNode = this.containsNode(dllData);
    if(null != foundNode)
    {
      returnValue = true;
    }
    return returnValue;
  } // public boolean contains(Record dllData)

/*********************************************************************
 * Method to return the node with a given data item in it, else null.
 * This method eliminates duplicate code in <code>contains</code>
 * and <code>remove</code>. 
 * @param dllData the <code>Record</code> to match against. 
 * @return the <code>DLLNode</code> answer, else null.
**/
  public DLLNode containsNode(Record dllData)
  {
    DLLNode returnValue = null;
    DLLNode currentNode = null;

    currentNode = this.getHead();
    currentNode = currentNode.getNext();
    while(currentNode != this.getTail())
    {
      if(0 == currentNode.getNodeData().compareTo(dllData))
      {
        returnValue = currentNode;
        break; // we violate the style rule
      }
      currentNode = currentNode.getNext();
    }

    return returnValue;
  } // public DLLNode containsNode(Record dllData)

/*********************************************************************
 * Method to remove a node with a given record as data. 
 * @param dllData the <code>Record</code> to match against. 
 * @return the <code>boolean</code> as to whether the record was
 *         found and removed or not.
**/
  public boolean remove(Record dllData)
  {
    boolean returnValue = false;
    DLLNode foundNode = null;
    foundNode = this.containsNode(dllData);
    if(null != foundNode)
    {
      this.unlink(foundNode);
      returnValue = true;
    }
    return returnValue;
  } // public boolean remove(Record dllData)

/*********************************************************************
 * Method to link a node before a given node. 
 * @param baseNode the <code>DLLNode</code> to be linked before. 
 * @param newNode the <code>DLLNode</code> to be linked in. 
**/
  private void linkBefore(DLLNode baseNode, DLLNode newNode){
	  
	 
	  newNode.setNext(baseNode);
	  newNode.setPrev(baseNode.getPrev());
	  
	  baseNode.getPrev().setNext(newNode);
	  baseNode.setPrev(newNode);
	  
	  size++;

	  
	 
	  
  } // private void linkBefore(DLLNode baseNode, DLLNode newNode)

/*********************************************************************
 * Method to <code>toString</code> a complete DLL, including head and
 * tail nodes.
 * @return the <code>toString</code> rep'n of the entire DLL.
**/
  public String toString()
  {
    int sequence;
    String s = "";
    DLLNode node;

    s += String.format("There are %d entries plus dummy head and tail%n", 
                       this.getSize()-2);
//    s += String.format("going forward%n");

// note that we include the head and then also the tail
    sequence = 0;
    node = this.head;
    s += String.format("%3d: %s%n", sequence, node.toString());
    while(node != tail)
    {
      node = node.getNext();
      ++sequence;
      s += String.format("%3d: %s%n", sequence, node.toString());
    }

    s += "\n";
/*
This was in my sample code, but we don't need it here.
    s += String.format("going backward%n");
    sequence = 0;
    node = this.tail;
    s += String.format("%3d: %s%n", sequence, node.toString());
    while(node != head)
    {
      node = node.getPrev();
      ++sequence;
      s += String.format("%3d: %s%n", sequence, node.toString());
    }
*/

    return s;
  } // public String toString()

/*********************************************************************
 * Method to unlink a node.
 * @param node the <code>DLLNode</code> to unlink.
**/
  private void unlink (DLLNode node)
  {
    node.getNext().setPrev(node.getPrev());
    node.getPrev().setNext(node.getNext());

    node.setNext(null);
    node.setPrev(null);

    this.decSize();
  } // private void unlink(DLLNode node)

} // public class DLL implements IDLL
